#include <iostream>
#include <unordered_map>

namespace {

struct ListNode {
    int val, key;
    ListNode *next;
    ListNode *prev;
    ListNode(int val, ListNode *next=NULL, ListNode *prev=NULL):val(val),next(next),prev(prev){}
};

ListNode* ReverseList(ListNode *head) {
    ListNode *curr = NULL;
    while(head) {
        curr = head;
        head = curr->next;
        curr->next = curr->prev;
        curr->prev = head;
    }
    return curr;
} 

void PrintList(const ListNode *head) {
    while(head) {
        std::cout << head->val << ",";
        head = head->next;
    }
    std::cout << std::endl;
}

struct DList {
    ListNode *head;
    ListNode *tail;
    int size;
    DList():size(0),head(NULL),tail(NULL){}
};

void PrintKV(const DList *list) {
    ListNode *head = list->head;
    while(head) {
        std::cout << head->key << ":" << head->val << ",";
        head = head->next;
    }
    std::cout << std::endl;
}

void AddNodeHead(DList *list, int val) {
    ListNode *node = new ListNode(val);
    if (list->size == 0) {
        list->head = node;
        list->tail = node;
    }
    else {
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->size++;
}

void AddNodeTail(DList *list, int val) {
    ListNode *node = new ListNode(val);
    if (list->size == 0) {
        list->head = node;
        list->tail = node;
    }
    else {
        node->prev = list->tail;
        list->tail->next = node;
        list->tail = node;
    }
    list->size++;
}

void RemoveNodeTail(DList *list) {
    if (list->size == 0) {
        return;
    }

    ListNode *node = list->tail;
    if (list->size == 1) {
        list->head = NULL;
        list->tail = NULL;
    }
    else {
        list->tail = list->tail->prev;
        list->tail->next = NULL;
    }

    delete node;
    list->size--;
}

void MoveToHead(DList *list, ListNode *node) {
    if (list->head == node) return;

    node->prev->next = node->next;
    if (node->next) {
        node->next->prev = node->prev;
    }
    else {
        list->tail = node->prev;
    }

    node->prev = NULL;
    node->next = list->head;
    list->head->prev = node;
    list->head = node;
}

typedef std::unordered_map<int, ListNode*> MapNode;
class LRUCache {
public:
    LRUCache(int cap): capacity(cap) {
        dlist = new DList();
    }
    ~LRUCache() {
    }
    void Put(int key, int val);
    int Get(int key);

    MapNode map;
    DList *dlist;
    int capacity;
};

void LRUCache::Put(int key, int val) {
    std::cout << "put " << key << ":" << val << " -> ";
    auto iter = this->map.find(key);
    if (iter == this->map.end()) {
        AddNodeHead(this->dlist, val);
        this->dlist->head->key = key;
        this->map[key] = this->dlist->head;

        if (this->map.size() > this->capacity) {
            this->map.erase(this->dlist->tail->key);
            RemoveNodeTail(this->dlist);
        }
    }
    else {
        iter->second->val = val;
        MoveToHead(this->dlist, iter->second);
    }
    PrintKV(this->dlist);
}

int LRUCache::Get(int key) {
    auto iter = this->map.find(key);
    if (iter == this->map.end())  {
        return -1;
    }
    MoveToHead(this->dlist, iter->second);
    return iter->second->val;
}

void Handle() {
    ListNode *list = new ListNode(0);
    ListNode *head = list;
    for (int i=1; i<10; i++) {
        ListNode *node = new ListNode(i);
        list->next = node;
        node->prev = list;
        list = node;
    }
    std::cout << "init list: ";
    PrintList(head);

    // 反转列表
    ListNode *reverseHead = ReverseList(head);
    std::cout << "resversed list: ";
    PrintList(reverseHead);

    DList *dlist = new DList();
    for (int i=0; i<10; i++) {
        AddNodeHead(dlist, i);
    }
    RemoveNodeTail(dlist);
    ListNode *node = dlist->head->next->next;
    MoveToHead(dlist, node);
    std::cout << "double list size " << dlist->size << std::endl;
    PrintList(dlist->head);

    LRUCache cache(3);
    cache.Put(1, 1);
    cache.Put(2, 2);
    cache.Put(3, 3);
    cache.Put(1, 4);
    cache.Put(4, 4);
    std::cout << "cache capacity " << cache.capacity << std::endl;
    std::cout << "cache key 1 val " << cache.Get(1) << std::endl;
    PrintKV(cache.dlist);
    std::cout << "cache key 2 val " << cache.Get(2) << std::endl;
    PrintKV(cache.dlist);
}

}

void HandleDList() {
    Handle();
}
